#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <functional>


// 此题之后，世界上将再无主动学习的链表
// 即将迎来的是
// 二叉树，并查集，迪杰斯特拉

struct ListNode
{
    int val;
    ListNode*next;
};

void add_node(ListNode*&head,int data)
{
    ListNode*node = new ListNode;
    node->val = data;
    node->next = nullptr;

    if (!head)
        head = node;
    else 
    {
        ListNode*temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = node;
    }
}

void print_list(ListNode*head)
{
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<"\n";
        temp = temp->next;
    }
}

// 思路1 利用已经学过的知识进行探索
// 这种方案的时间复杂度是 O(n+k) k为min与max的差值
// 虽然面向STL编程有点被束缚的感觉，但是我只打印这一次
// STL永远比手写效率要高
// 合并k个数组也可以使用最小堆

ListNode* raw_merge_list(std::vector<ListNode*>&v)
{
    // 合并链表不意味着把节点进行重排，如果使用哈希表统计值的个数，然后把链表拼到一起
    // 然后使用count--来改变所有节点的值
    
    //先合并n个链表
    int n = v.size();
    ListNode*head = v[0];
    for (int i = 0;i < n-1;i++)
    {
        ListNode*temp = v[i];
        if (!temp)
        {
            continue;
        }
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = v[i+1];
    }

    // 计算值的个数 
    // 找到最大值与最小值？？？
    int max_ = 0;
    int min_ = 100000000;
    std::unordered_map<int,int>mp;
    ListNode*temp = head;
    while (temp)
    {
        mp[temp->val]++;
        if (temp->val>max_)
        {
            max_ = temp->val;
        }
        if (temp->val < min_)
        {
            min_ = temp->val;
        }
        temp = temp->next;
    }

    // 按照值的个数对节点들进行重新赋值
    temp = head;
    for (int i = min_;i <= max_;i++)
    {
        if (mp.find(i) == mp.end())
        {
            continue;
        }
        int count = mp[i];
        while (count--)
        {
            temp->val = i;
            temp = temp->next;
        }
    }

    // 又来了，自以为没有问题

    // 完美地返回头节点
    return head;
}

// 思路2 利用船新内容最小堆进行解决
struct Compare
{
    bool operator()(ListNode*&a,ListNode*&b)
    {
        return a->val > b->val;
    }
};

ListNode* merge_list(std::vector<ListNode*>&v)
{
    // 多次判空
    if (v.empty())
    {
        return nullptr;
    }

    // 创建优先队列
    std::priority_queue<ListNode*,std::vector<ListNode*>,Compare>pq;

    // 创建哑节点结果节点
    ListNode*dummy = new ListNode;


    // 将所有节点加入队列
    for (auto node:v)
    {
        if (node)
        {
            pq.push(node);
        }
    }

    // 使用while循环进行遍历
    ListNode*curr = dummy;
    while (!pq.empty())
    {
        // 这里逻辑很复杂，但是尽量把需要删除的东西记录一下
        ListNode*temp = pq.top();
        pq.pop();

        // 将最小节点连接到结果
        curr ->next = temp;
        curr = curr->next;

        // 将后续不为空的节点加入最小堆
        // 这里特别牛逼，始终保证pq中节点数量小于等于k
        if (temp->next)
        {
            pq.push(temp->next);
        }

    }

    return dummy->next;
}

// 现在为什么就可以了
// 那暑假时候，难道是类和结构体不一样？？？？

int main()
{
    ListNode*head1 = new ListNode;
    ListNode*head2 = new ListNode;
    ListNode*head3 = new ListNode;
    head1->val = 1;
    head2->val = 2;
    head3->val = 1;

    for (int i = 0;i < 10;i ++)
    {
        add_node(head1,i+3);
        add_node(head2,i+2);
        add_node(head3,i+3);
    }

    std::vector<ListNode*>v;
    v.push_back(head1);
    v.push_back(head2);
    v.push_back(head3);

    ListNode*head = raw_merge_list(v);
    print_list(head);
    return 0;
}